A packet switching network comprises an array of packet switches interconnected by packet channels. Each packet channel connects two such packet switches. Typically, packets are routed through the network synchronously in time slots.
A packet switch in a broadband packet switching network is expected to have a throughput of several tens of Gigabits per second. An example of such a packet switch is described in "Batcher-Banyan Packet Switch With Output Conflict Resolution Scheme", U.S. patent application Ser. No. 919,793 filed for E. Arthurs and J. Hui on Oct. 16, 1986 and assigned to the assignee hereof, now U.S. Pat. No. 4,817,084, issued Mar. 28, 1989.
To cope with high bit rate data streams, the lower layer communications protocols must be simplified. Simplification is achievable because of the high speed and low error rate qualities of fiber optic links. Dynamic Time Division Multiplexing (see e.g., "Dynamic Time Division Multiplexing", U.S. patent application Ser. No. 118,977, filed on Nov. 10, 1987 for H. J. Chao, S. H. Lee and L. T. Wu and assigned to the assignee hereof) and Asynchronous Time Division Multiplexing (see e.g., T. A. Coudreuse, J. P. Servel "Asynchronous Time-Division Techniques: An Experimental Packet Network Integrating Video Communications. Proceedings of International Switching Symposium, Florence, Italy, 1984 paper 32.C.2.). provide simple data link layer protocols for broadband packet switching networks.
However, high throughput switches and efficient data link protocols alone do not guarantee an effective transport system. It is important to be able to allocate bandwidth so that resources are efficiently utilized and congestion is kept under control. This is a difficult problem because the traffic characteristics of potential broadband services are uncertain and the capacity of each packet channel has an upper bound related to technology limits (i.e. the maximum bit rate allowed by current technology) and to processing requirements per packet (e.g. the time required for a switch or a multiplexer to process a packet, typically on the order of a few microseconds). Furthermore, the peak rate of traffic sources varies by several orders of magnitude, with peak demands that may approach or exceed the capacity of a single packet channel. Thus additional protocols are needed to support service rates that exceed the capacity of a single packet channel.
In a packet network, connections between specific users are achieved by means of virtual circuits. Each virtual circuit typically passes through a plurality of packet switches and packet channels therebetween. A virtual circuit has to be set up before the transfer of user information takes place via the virtual circuit. To set up a virtual circuit, an appropriate amount of bandwidth is reserved for the virtual circuit in the particular packet channels and packet switches comprising the virtual circuit.
More particularly, to set up a virtual circuit in a packet network, a sequence of connections between pairs of packet switches is established. Upon receiving a connection request, a packet switch S.sub.1 acts as follows. According to a routing strategy such as Dynamic Non-Hierarchical Routing, the packet switch S.sub.1 chooses the next adjacent packet switch S.sub.2 in the virtual circuit. Then, out of the set of packet channels connecting the packet switches S.sub.1 and S.sub.2 a particular packet channel is chosen for the virtual circuit depending for example on the bandwidth already reserved on the packet channels between switches S.sub.1 and S.sub.2 and the expected traffic characteristics of the new connection.
A classical problem is the optimal allocation of virtual circuits to specific channels of a transmission facility to improve throughput and reduce delay. This becomes a critical issue when the peak rate of a traffic source is close to the channel capacity. An allocation policy that uniformly books (and loads) the packet channels between two adjacent packet switches minimizes the average delay for each connection but penalizes the establishment of high bandwidth connections because the requested bandwidth is likely to exceed the residual usable capacity of each single channel. Alternatively, a scheme assigning a virtual connection to the fullest channel that can accommodate the new bandwidth request minimizes the blocking probability of high-peak throughput sources, but does not optimize delay.
In view of the foregoing, it is an object of the present invention to provide a more efficient method for allocating bandwidth in a broadband packet switching network.